class Solution {
public:
    int maxDistance(vector<int>& position, int m)
    {
        ranges::sort(position);
        auto check = [&](int mid) {
            int cnt = 1, pre = position[0];
            for (auto e : position)
            {
                if (e >= pre + mid)
                {
                    cnt++;
                    pre = e;
                }
            }
            return cnt >= m;
            };

        int left = 1, right = 1e9;
        while (left < right - 1)
        {
            int mid = left + (right - left) / 2;
            (check(mid) ? left : right) = mid;
        }
        return left;
    }
};